1. Field of the Invention
This invention relates to the field of digital systems employing non-volatile memory and particularly flash memory as mass storage for computers, digital cameras and the like.
2. Description of the Prior Art
Recently, solid state memory has gained popularity for use in replacing mass storage units in various technology areas such as computers, digital cameras, modems and the like. For example, in digital cameras, the use of solid state memory, such as flash memory, replaces conventional films.
Flash memory is generally provided in the form of semiconductor devices (or chips) with each device made of a large number of transistor memory cells and each cell being individually programmable. The programming (or writing) and erasing of such a memory cell is limited to a finite number of erase-write cycles, which basically determines the lifetime of the device. Furthermore, an inherent characteristic of flash memory cells is that they must be erased and verified for successful erase prior to being programmed.
With the use of flash memory, however, the area of memory that once contained information must first be erased prior to being re-programmed. In a flash memory device, write and erase cycles are generally slow and can significantly reduce the performance of a system utilizing flash memory as its mass storage.
In applications employing flash memory devices, such as personal computers and digital cameras, a host writes and reads information to the flash memory devices through a controller device, which is commonly in the form of a semiconductor device. Such information is organized in sectors with each sector including user data information and overhead information and being generally 512 bytes in length. The controller, upon receiving sector information from the host, during a host-commanded write operation, writes the information to the flash memory devices in accordance with a predetermined sector organization. While the host may be accessing multiple sectors, each sector is written to the flash devices one at a time.
Currently, in computers wherein large files such as commercial software and user programs are stored within flash memory and in digital cameras wherein large picture files are stored within flash devices, the files are written one sector at a time within flash. Due to the latency associated with each write operation, the performance of these systems when storing large quantities of information is limited.
In storing and/or retrieving a data file (data files may be any computer files including commercial software, user program, word processor software document, spread sheet file and the like), a computer (or host) system provides what is referred to as the logical block address indicating the location of where the host believes the data file to exist within the mass storage. The host-provided address may be in the form of cylinder, head and sector (CHS), which is converted to a logical block address format upon receipt by the controller. The same applies to digital camera applications. The controller then translates the logical block address (LBA) into a physical block address (PBA) and uses the latter to access the data file within flash memory. Each time a data file is changed, the latest version of the file is stored in an available (or `unused`) location within the flash memory that is identified by a new physical location (or new PBA). Upon using much of the free or available locations within the flash memory for updated files, an erase operation may be needed to make available `old` locations for storage of additional information. Since erase operations are time-consuming (as are write operations), there is a trade-off as to the frequency of performing erase operations to the time expended for searching for free locations within the flash memory as more and more locations are used prior to the next erase operation.
A variety of different algorithms may be employed for determining when an erase operation(s) will take place and as a function thereof, where within the flash memory (mass storage the next available free block is located for storing the data file. The space manager unit of the controller device performs this function.
Information in the nonvolatile memory or flash memory or stored under the direction of the controller and it is done so in the form of blocks. Thus, information that is stored in nonvolatile memory is organized in blocks and each block is uniquely addressable by the controller. Each block is further comprised of multiple sectors with each sector defining 512 bytes of storage space. In some prior art systems, during an erase operation, an entire block is erased whereas in other prior art systems, the sector may be erased. Each block is uniquely addressable for reading and writing information from and to the nonvolatile memory. Each sector includes information such as data, flags and Error Correction Codes (ECC). The address of block within the nonvolatile memory is maintained within the respective block for use in reconstructing the addressing or mapping information associated with the nonvolatile memory after a power-down. This mapping information is the contents of a look-up-table maintained in volatile memory, as will now be further described.
The space manager unit of the controller device maintains a table of information regarding the location of the most recent data within the flash memory in addition to the location of information that is considered `old` (information which has been superseded) and no yet erased and/or `defective` (location can not be used for storing information due to some kind of defect) or `used` (currently contains up-to-date information). This table of information is stored and updated in a volatile memory location such as RAM either within or outside of the controller device. Each time information is accessed by the host, the space manager table is used to find out the location of the information that is to be written and/or read from the flash memory devices.
The problem with prior art methods and apparatus using nonvolatile memory devices is that when, for example, a block of information within a particular nonvolatile memory device is being erased, another block within the same flash device cannot be erased. This is, in part, due to the nonvolatile memory devices being busy erasing the previous block. During the erase operation of the particular nonvolatile memory device, the Ready/Busy* signal is at logic state `0` indicating the particular nonvolatile memory device to be busy but this also means that another block within the same device cannot be erased. Consequently, each block of each nonvolatile memory device has to be erased serially, i.e. one at a time.
Erase operations of nonvolatile memory devices, such as flash devices, are generally time consuming thereby substantially degrading the overall performance of a system in which the nonvolatile memory is employed. Furthermore, as the number of blocks being accessed grows, there is further degradation of the system due to the even more lengthy process of erasing a large number of blocks. For example, generally, after an update (or a re-write operation) of a block, an erase operation is performed of an `old` block and when only one block must be erased completely prior to performing erase of another block, the time spent for performing erase operations in general becomes excessive. The latter is due to the limitation of prior art systems that erase blocks serially, as discussed above.
There is therefore a need within digital systems using solid state memory such as flash devices to decrease the amount of time associated with erase operations thereby increasing system performance.